package com.nl.trees;

import com.nl.trees.BTree.Node;

public class BSTConvertLinkedList {
	
	public static class LastNode<T>{
		Node<T> lastNodeInList;
	}
	public static <T> Node<T>  convert(BTree<T> tree){
		
		LastNode<T> lastNode=new LastNode<T>();

		convertNode(tree.root,lastNode);

		Node<T> headOfList = lastNode.lastNodeInList;
		while(headOfList!=null && headOfList.left!=null){
			headOfList = headOfList.left;
		}

		return headOfList;
	}
	
	public static <T> void convertNode(Node<T> proot,LastNode<T> lastNode){
		
		if(proot == null){
			return;
		}
		
		Node<T> current = proot;
		if(current.left !=null){
			convertNode(current.left, lastNode);
		}
		current.left = lastNode.lastNodeInList;

		if(lastNode.lastNodeInList!=null){
			lastNode.lastNodeInList.right = current;
		}

		lastNode.lastNodeInList = current;
		
		if(current.right !=null){
			convertNode(current.right, lastNode);
		}
	}

}
